package com.breeze.leetcode;

import java.util.ArrayList;

/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class LeetCode236 {
    /**
     * 方法一：广度优先搜索+递归
     * <p>
     * 这个代码就是傻逼
     */
    // 一个树包含p,q，且左右子树均无法同时包含p,q，则该树的根节点为LCA
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        // 广度优先搜索,用来查找是否同时包含p,q
        boolean hasP = false, hasQ = false;
        ArrayList<TreeNode> list = new ArrayList();
        list.add(root);
        while (!(hasP && hasQ) && !list.isEmpty()) {
            TreeNode node = list.remove(0);
            if (node == p) hasP = true;
            if (node == q) hasQ = true;
            if (node.left != null) list.add(node.left);
            if (node.right != null) list.add(node.right);
        }
        if (hasP && hasQ) {
            // 左右子树各自不包含p,q时，当前root节点即为结果
            TreeNode node1 = lowestCommonAncestor(root.left, p, q);
            if (node1 != null) return node1;
            TreeNode node2 = lowestCommonAncestor(root.right, p, q);
            if (node2 != null) return node2;
            return root;
        } else {
            // 不包含则返回空
            return null;
        }
    }

    /**
     * 方法二： 递归
     * 若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：
     * p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
     * p = root，且 q 在 root 的左或右子树中；
     * q = root，且 p 在 root 的左或右子树中；
     * <p>
     * 时间复杂度：O(n) 每个节点都会遍历
     * 空间复杂度：O(n) 最差情况下，递归深度达到 n ，系统使用 O(n) 大小的额外空间。
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        // root为null，说明无p,q，返回null
        if (root == null) {
            return null;
        }
        // 等于p,或q说明包含p或q
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left, p, q); // 查找左子树是否包含p或q节点
        TreeNode right = lowestCommonAncestor1(root.right, p, q); // 查找右子树是包含在p或q节点
        // 左右子树均不包含，则整个树无LCA
        if (left == null && right == null) return null;
        // 左子树包含，右子树不包含，则该left为LCA
        if (left != null && right == null) return left;
        // 右子树包含，左子树不包含，则该right为LCA
        if (right != null && left == null) return right;
        // 左右子树均包含，则p,q在左右子树上，则这个root节点为LCA
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        // [6,2,8,0,4,7,9,null,null,3,5]
        TreeNode root = new TreeNode(6);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(8);
        TreeNode node3 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(7);
        TreeNode node6 = new TreeNode(9);
        TreeNode node7 = new TreeNode(3);
        TreeNode node8 = new TreeNode(5);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;
        LeetCode236 leetCode236 = new LeetCode236();
        System.out.println(leetCode236.lowestCommonAncestor(root, node1, node2).val); // 6
        System.out.println(leetCode236.lowestCommonAncestor(root, node1, node4).val); // 2
        System.out.println(leetCode236.lowestCommonAncestor1(root, node1, node2).val); // 6
        System.out.println(leetCode236.lowestCommonAncestor1(root, node1, node4).val); // 2
    }
}
